package p03_SingleLinkedList.quiz.q06_JosephusProblem;


import org.junit.jupiter.api.Test;

//Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public int josephusList(int n, int m) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        // 创建循环单向链表
        for (int i = 1; i < n; i++) {
            p.next = new ListNode(i);
            p = p.next;
        }
        p.next = head;
        p = head;
        while (p.next != p) {
            for (int i = 1; i < m; i++) {
                p = p.next;
            }
            p.val = p.next.val;
            p.next = p.next.next;
        }
        return p.val;
    }

    public int josephusList1(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = josephusList1(n - 1, m);
        System.out.println(x);
        int res =  (x + m) % n;
        return res;
    }

    @Test
    public void test01() {
        int res = josephusList1(5, 3);
        System.out.println(res);
    }
}
